#ifndef MST_H_
#define MST_H_

#include <algorithm>
#include <array>
#include <queue>
#include <utility>
#include <vector>

namespace lxj
{
// Kruskal算法模版（洛谷）
// 静态空间实现
// 测试链接 : https://www.luogu.com.cn/problem/P3366
class Kruskal {
    std::vector<int> father;

    inline int find(int i)
    {
        if (i != father[i]) father[i] = find(father[i]);
        return father[i];
    }

    inline bool isSameSet(int a, int b) { return find(a) == find(b); }
    inline void unionSet(int a, int b) { father[find(a)] = find(b); }

public:
    inline int kruskal(int n, std::vector<std::array<int, 3>>& ways)
    {
        father = std::vector<int>(n + 1);
        for (int i = 0; i < n + 1; i++) {
            father[i] = i;
        }

        using array3 = std::array<int, 3>;
        auto my_comp = [](const auto& a, const auto& b) { return a[2] > b[2]; };
        std::priority_queue<array3, std::vector<array3>, decltype(my_comp)> queue(my_comp, ways);

        int ans   = 0;
        int edges = 0;
        while (!queue.empty()) {
            const array3& cur = queue.top();
            if (!isSameSet(cur[0], cur[1])) {
                ans += cur[2];
                edges++;
                unionSet(cur[0], cur[1]);
            }
            queue.pop();
        }
        return edges == n - 1 ? ans : -1;
    }
};

// Prim算法模版（无优化版） O(n+m)+O(m * log m)
// 动态空间实现
// 测试链接 : https://www.luogu.com.cn/problem/P3366
inline int prim1(int n, std::vector<std::array<int, 3>>& ways)
{
    std::vector<std::vector<std::pair<int, int>>> graph(n + 1);
    for (const auto& way : ways) {
        graph[way[0]].push_back({way[1], way[2]});
        graph[way[1]].push_back({way[0], way[2]});
    }

    using array2 = std::pair<int, int>;
    auto my_comp = [](const auto& a, const auto& b) { return a.second > b.second; };
    std::priority_queue<array2, std::vector<array2>, decltype(my_comp)> heap(my_comp);
    for (auto& edge : graph[1]) {
        heap.push(edge);
    }

    bool* set = new bool[n + 1];
    std::fill(set, set + n + 1, false);
    int nodeCnt = 1;
    set[1]      = true;
    int ans     = 0;
    while (!heap.empty()) {
        const array2& edge = heap.top();
        int           next = edge.first;
        int           cost = edge.second;
        heap.pop();
        if (set[next] == false) {
            ans += cost;
            nodeCnt++;
            set[next] = true;
            for (auto& e : graph[next]) heap.push(e);
        }
    }
    delete[] set;
    return nodeCnt == n ? ans : -1;
}

// Prim算法优化（洛谷）
// 静态空间实现
// 时间复杂度O(n + m) + O((m+n) * log n)
// 测试链接 : https://www.luogu.com.cn/problem/P3366
// 需要调整堆结构，所以要自己手写堆
class Prim {
    inline constexpr static int MAXN = 5001;
    inline constexpr static int MAXM = 400001;
    inline static int           n = 0, m = 0;

    // 链式前向星
    inline static std::vector<int> head   = std::vector<int>(MAXN);
    inline static std::vector<int> next   = std::vector<int>(MAXM);
    inline static std::vector<int> to     = std::vector<int>(MAXM);
    inline static std::vector<int> weight = std::vector<int>(MAXN);
    inline static int              cnt    = 0;

    // 改写的堆结构
    inline static std::vector<int[2]> heap = std::vector<int[2]>(MAXN);
    // where[v] = -1，表示v这个节点，从来没有进入过堆
    // where[v] = -2，表示v这个节点，已经弹出过了
    // where[v] = i(>=0)，表示v这个节点，在堆上的i位置
    inline static std::vector<int> where = std::vector<int>(MAXN);
    // 堆的大小
    inline static int heapSize = 0;
    // 找到的节点个数
    inline static int nodeCnt = 0;

    inline void build()
    {
        cnt      = 1;
        heapSize = 0;
        nodeCnt  = 0;
        std::fill(head.begin(), head.begin() + n + 1, 0);
        std::fill(where.begin(), where.begin() + n + 1, -1);
    }

    inline void addEdge(int u, int v, int w)
    {
        next[cnt]   = head[u];
        to[cnt]     = v;
        weight[cnt] = w;
        head[u]     = cnt++;
    }

    inline void addOrUpdateOrIgnore(int ei)
    {
        int v = to[ei];
        int w = weight[ei];
        if (where[v] == -1) {
            heap[heapSize][0] = v;
            heap[heapSize][1] = w;
            where[v]          = heapSize++;
            heapInsert(where[v]);
        }
        else if (where[v] > 0) {
            heap[where[v]][1] = std::min(heap[where[v]][1], w);
            heapInsert(where[v]);
        }
    }

    inline void heapInsert(int i)
    {
        while (heap[i][1] < heap[(i - 1) / 2][1]) {
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    inline void heapify(int i)
    {
        int l = i * 2 + 1;
        while (l < heapSize) {
            int best = l + 1 < heapSize && heap[l + 1][1] < heap[l][1] ? l + 1 : l;
            best     = heap[best][1] < heap[i][1] ? best : i;
            if (best == i) break;
            swap(best, i);
            i = best;
            l = i * 2 + 1;
        }
    }

    inline bool isEmpty() { return heapSize == 0; }

    inline static int u = 0;
    inline static int w = 0;

    inline void pop()
    {
        u = heap[0][0];
        w = heap[0][1];
        swap(0, --heapSize);
        heapify(0);
        where[u] = -2;
        nodeCnt++;
    }

    inline void swap(int i, int j)
    {
        int a      = heap[i][0];
        int b      = heap[j][0];
        where[a]   = j;
        where[a]   = i;
        int tmp[2] = {heap[i][0], heap[i][1]};
        heap[i][0] = heap[j][0];
        heap[i][1] = heap[j][1];
        heap[j][0] = tmp[0];
        heap[j][1] = tmp[1];
    }

public:
    inline int prim2(int n, std::vector<std::array<int, 3>>& ways)
    {
        Prim::n = n;
        m       = ways.size();
        build();
        for (const auto& way : ways) {
            addEdge(way[0], way[1], way[2]);
            addEdge(way[1], way[0], way[2]);
        }

        nodeCnt  = 1;
        where[1] = -2;
        for (int ei = head[1]; ei > 0; ei = next[ei]) {
            addOrUpdateOrIgnore(ei);
        }

        int ans = 0;
        while (!isEmpty()) {
            pop();
            ans += w;
            for (int ei = head[1]; ei > 0; ei = next[ei]) {
                addOrUpdateOrIgnore(ei);
            }
        }
        return ans;
    }
};

// 水资源分配优化
// 村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
// 对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井
// 成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）
// 另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，
// 其中每个 pipes[j] = [house1j, house2j, costj]
// 代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。
// 请返回 为所有房子都供水的最低总成本
// 测试链接 : https://leetcode.cn/problems/optimize-water-distribution-in-a-village/
class OptimizeWaterDistribution {
    inline constexpr static int MAXN = 10010;
    inline static auto edges = std::vector<std::array<int, 3>>(MAXN << 1, std::array<int, 3>());
    inline static int  father[MAXN] = {};
    inline static int  cnt          = 0;

    inline void build(int n)
    {
        cnt = 0;
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }

    inline int find(int i)
    {
        if (i != father[i]) father[i] = find(father[i]);
        return father[i];
    }

    inline bool unionSet(int a, int b)
    {
        int fx = find(a);
        int fy = find(b);
        if (fx != fy) {
            father[fx] = fy;
            return true;
        }
        return false;
    }

public:
    inline int minCostToSupplyWater(int                            n,
                                    std::vector<int>&              wells,
                                    std::vector<std::vector<int>>& pipes)
    {
        build(n);
        for (int i = 0; i < n; i++, cnt++) {
            edges[cnt][0] = 0;
            edges[cnt][1] = i + 1;
            edges[cnt][2] = wells[i];
        }
        for (int i = 0; i < pipes.size(); i++, cnt++) {
            edges[cnt][0] = pipes[i][0];
            edges[cnt][1] = pipes[i][1];
            edges[cnt][2] = pipes[i][2];
        }

        std::sort(edges.begin(), edges.begin() + cnt, [](const auto& a, const auto& b) {
            return a[2] < b[2];
        });
        int ans = 0;
        for (int i = 0; i < cnt; i++) {
            if (unionSet(edges[i][0], edges[i][1])) {
                ans += edges[i][2];
            }
        }
        return ans;
    }
};

// 检查边长度限制的路径是否存在
// 给你一个 n 个点组成的无向图边集 edgeList
// 其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边
// 请注意，两个点之间可能有 超过一条边 。
// 给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj]
// 你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径
// 且这条路径上的每一条边都 严格小于 limitj 。
// 请你返回一个 布尔数组 answer ，其中 answer.length == queries.length
// 当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false
// 测试链接 : https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/
class CheckingExistenceOfEdgeLengthLimit {
    inline constexpr static int MAXN         = 100001;
    inline static int           father[MAXN] = {};

    std::vector<std::vector<int>> questions;

    inline void build(int n)
    {
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }

    inline int find(int i)
    {
        if (i != father[i]) father[i] = find(father[i]);
        return father[i];
    }

    inline bool isSameSet(int a, int b) { return find(a) == find(b); }

    inline void unionSet(int a, int b) { father[find(a)] = find(b); }

public:
    inline std::vector<bool> distanceLimitedPathsExist(int                            n,
                                                       std::vector<std::vector<int>>& edgeList,
                                                       std::vector<std::vector<int>>& queries)
    {
        int m     = edgeList.size();
        int k     = queries.size();
        questions = std::vector<std::vector<int>>(k, std::vector<int>(4));
        build(n);

        std::sort(edgeList.begin(), edgeList.end(), [](const auto& a, const auto& b) {
            return a[2] < b[2];
        });
        for (int i = 0; i < k; i++) {
            questions[i][0] = queries[i][0];
            questions[i][1] = queries[i][1];
            questions[i][2] = queries[i][2];
            questions[i][3] = i;
        }

        std::sort(questions.begin(), questions.end(), [](const auto& a, const auto& b) {
            return a[2] < b[2];
        });

        std::vector<bool> ans(k);
        for (int i = 0, j = 0; i < k; i++) {
            for (; j < m && edgeList[j][2] < questions[i][2]; j++) {
                unionSet(edgeList[j][0], edgeList[j][1]);
            }
            ans[questions[i][3]] = isSameSet(questions[i][0], questions[i][1]);
        }

        return ans;
    }
};

// 繁忙的都市
// 一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造
// 城市的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连
// 两个交叉路口之间最多有一条道路相连接，这些道路是双向的
// 且把所有的交叉路口直接或间接的连接起来了
// 每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造
// 但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
// 1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来
// 2. 在满足要求1的情况下，改造的道路尽量少
// 3. 在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小
// 作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建
// 返回选出了几条道路 以及 分值最大的那条道路的分值是多少
// 测试链接 : https://www.luogu.com.cn/problem/P2330
class BusyCities {
    inline constexpr static int MAXN = 301;
    inline constexpr static int MAXM = 8001;

    inline static int father[MAXN] = {};

    inline void build(int n)
    {
        for (int i = 0; i <= n; i++) father[i] = i;
    }

    inline int find(int i)
    {
        if (i != father[i]) father[i] = find(father[i]);
        return father[i];
    }

    inline bool unionSet(int a, int b)
    {
        int fx = find(a);
        int fy = find(b);
        if (fx != fy) {
            father[fx] = fy;
            return true;
        }
        return false;
    }

public:
    inline std::pair<int, int> busyCities(int n, std::vector<std::vector<int>>& edges)
    {
        build(n);
        std::sort(
            edges.begin(), edges.end(), [](const auto& a, const auto& b) { return a[2] < b[2]; });

        int max    = 0;
        int endCnt = 0;
        for (int i = 0; i < n; i++) {
            if (unionSet(edges[i][0], edges[i][1])) {
                endCnt++;
                max = std::max(max, edges[i][2]);
            }
            if (endCnt == n - 1) break;
        }
        return {n - 1, max};
    }
};

}   // namespace lxj

#endif